#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int numDistinct(string S, string T) {
        int n=S.size(), m=T.size();
        if (n==0 || m==0) return 0;
        vector< vector<int> > f(n+1, vector<int>(m+1,0));
        f[0][0]=1;
        for (int i=1;i<=m;i++)
            f[0][i]=0;
        for (int i=1;i<=n;i++) {
            f[i][0]=1;
            for (int j=1;j<=m;j++) {
                f[i][j]=f[i-1][j];
                if (S[i-1]==T[j-1]) f[i][j]+=f[i-1][j-1];
            }
        }
        return f[n][m];
    }
};
